﻿#include <iostream>
#include <string>
using namespace std;
template <typename T>
class listNode//节点类定义
{
public:
	listNode() { next = NULL; }
	T data;//节点中的数据部分
	listNode* next;//指向下一个节点的指针
};
template <typename T>
class linkedList
{
private:
	int listlength;
	listNode<T>* node;//当前节点指针,指向下一个节点
	listNode<T>* lastnode;//尾结点指针
	listNode<T>* headnode;//头结点指针
public:
	linkedList();
	int length();//获取当前链表长度
	void add(T x);//增加一个节点到尾
	void traversal();//遍历链表+输出各个节点的data
	bool isEmpty();//链表是否为空
	void Delete(T x);//删除某个值为X的节点;
	void insert(T x, listNode<T>* p);
	void insertHead(T x);//逆向链表创建操作
	listNode<T>* search(T x);//寻找值为x的节点，用于测试两个insert函数
};
template<typename T>
linkedList<T>::linkedList()
{
	listlength = 0;
	node = NULL;
	headnode = NULL;
	lastnode = NULL;
}
template<typename T>
int linkedList<T>::length()
{
	listNode<T>* p;
	p = headnode;
	int len = 0;
	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	return len;
}
template <typename T>
void linkedList<T>::add(T x)
{
	listNode<T>* p = new listNode<T>;
	if (headnode == NULL)
	{
		headnode = p;//如果链表为空，则头，当前，尾都指向新创建的节点
		node = p;
		lastnode = p;
		p->data = x;
	}
	else
	{
		lastnode->next = p;
		lastnode = p;
		p->data = x;
	}
	/*node->next = p;//链表尾结点的指针指向当前节点，完成add操作
	p->node->next = NULL;//尾结点的next指向空
	p->node->data = x;*/
}
template <typename T>
void linkedList<T>::traversal()
{
	listNode<T>* p;
	p = headnode;
	int i = 0;
	if (p == NULL)
	{
		cout << "The list is empty" << endl;
	}
	while (p != NULL)
	{
		i++;
		cout << "The " << i << " th node's data is: " << p->data << endl;
		p = p->next;
	}
}
template <typename T>
bool linkedList<T>::isEmpty()
{
	if (headnode == NULL)
		return true;
	else 
		return false;
}
template <typename T>
void linkedList<T>::Delete(T x)
{
	listNode<T>* p;
	listNode<T>* pre;
	p = headnode;
	pre = p;
	int len = 0, flag = 0;//flag表示是找到并且删除，如果flag==0则没有删除
	while ((p != NULL))//遍历链表，直到所有的目标节点都被删除
	{
		len++;
		pre = p;
		if (p->data == x)
		{
			flag = 1;
			pre->next = p->next;
			if (p == headnode)//如果删除的节点是头节点 则头结点下移
			{
				headnode = p->next;
			}
			if (p == lastnode)//如果删除的节点是尾结点，则尾结点上移
			{
				lastnode = pre;
			}
		}
		p = p->next;
	}
	if ((p == NULL)&&(flag==0))//遍历到最后也没找到要删除的节点
	{
		cout << "The element you want to delete is not in the list." << endl;
	}
}
template <typename T>
void linkedList<T>::insert(T x, listNode<T>* p)
{
	listNode<T>* cur = headnode;
	while ((cur != NULL) && (cur!=p))
	{
		cur = cur->next;
	}
	if ((cur == NULL) && (cur->data != x))
	{
		cout << "No target node,insert failure" << endl;
	}
	else if (cur != NULL)
	{
		listNode<T>* insertNode = new listNode<T>;
		insertNode->data = x;
		insertNode->next = cur->next;
		cur->next = insertNode;
	}
}
template<typename T>
void linkedList<T>::insertHead(T x)
{
	listNode<T>* cur = new listNode<T>;
	cur->data = x;
	cur->next = headnode;
	headnode = cur;
}
template<typename T>
listNode<T>* linkedList<T>::search(T x)
{
	listNode<T>* cur = headnode;
	while ((cur != NULL) )
	{
		if (cur->data != x)
		{
			cout << "hadshsadhf" << endl;
			cout << cur->data << endl;
			cur = cur->next;
		}
		else
		{
			cout << "cur->data is: " << cur->data << endl;
			return cur;
		}
	}
	if (cur == NULL)
	{
		cout << "No target node" << endl;
		return NULL;
	}
	else
	{
		return cur;
	}
}
int main()
{
	linkedList<string> l1;
	cout << l1.isEmpty() << endl;
	l1.add("abc");
	l1.add("abc");//两个相同数据为了测试是否能删除所有符合条件的节点
	l1.add("c");
	cout << l1.length() << endl;
	l1.traversal();
	l1.Delete("abc");//测试是否能头结点上移，并且删除所有符合条件的节点
	l1.traversal();
	listNode<string>* cur = l1.search("c");
	if (cur!= NULL)
	{
		l1.insert("123", cur);
	}
	else
	{
		cout << "cur is NULL" << endl;
	}
	l1.traversal();
	l1.insertHead("head");
	l1.traversal();
}